import java.util.*;

public class MyBinaryTree {
    public class treeNode{
        public char val;
        public treeNode left;
        public treeNode right;

        public treeNode(char val) {
            this.val = val;
        }
    }

    public treeNode createBinaryTree() {
        treeNode A = new treeNode('A');
        treeNode B = new treeNode('B');
        treeNode C = new treeNode('C');
        treeNode D = new treeNode('D');
        treeNode E = new treeNode('E');
        treeNode F = new treeNode('F');
        treeNode G = new treeNode('G');
        treeNode H = new treeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        E.right = H;
        C.left = F;
        C.right = G;

        return A;
    }


    // 前序遍历
    public void preOrder(treeNode root){
        if(root == null) return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    public void preOrderNor(treeNode root){
        if(root == null) return;
        Stack<treeNode> stack = new Stack<treeNode>();
        treeNode cur = root;


        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            treeNode top = stack.pop();
            cur = top.right;
        }
    }

    // 中序遍历
    void inOrder(treeNode root){
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    // 后序遍历
    void postOrder(treeNode root){
        if(root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
    //非递归写法
    public void postOrderNor(treeNode root){
        if(root == null) return;
        Stack<treeNode> stack = new Stack<>();

        treeNode cur = root;
        treeNode prev = null;

        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            treeNode top = stack.peek();
            if (top.right == null || top.right == prev) {
                System.out.print(top.val + " ");
                stack.pop();
                prev = top;
            } else {
                cur = top.right;
            }
        }

    }

    // 获取树中节点的个数
    //思路1：遍历思路
    public static int nodeSize;
    public void size(treeNode root){
        if(root == null) return;
        nodeSize++;
        size(root.left);
        size(root.right);
    }
    //思路二：子问题解决，叶子节点个数 = 左子树节点个数 + 右子树节点个数 + 1
    public int size2(treeNode root){
        if(root == null) return 0;

        return size2(root.left) +
                size2(root.right) + 1;
    }

    // 获取叶子节点的个数
    //思路一:遍历法
    public static int leafSize;
    public void getLeafNodeCount(treeNode root){
        if(root == null){
            return;
        }
        if(root.right == null && root.left == null){
            leafSize++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
    }
    //子问题思路-求叶子结点个数
    public int getLeafNodeCount2(treeNode root){
        if(root == null){
            return 0;
        }
        if(root.right == null && root.left == null){
            return 1;
        }
        return getLeafNodeCount2(root.left) +
        getLeafNodeCount2(root.right);
    }


    // 获取第K层节点的个数
    //思路：每递归一次到子树，k都-1，当k == 1时,即可求解
    public int getKLevelNodeCount(treeNode root,int k){
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1) +
                getKLevelNodeCount(root.right,k-1);
    }

    // 获取二叉树的高度
    //思路：总高度 = 左子树高度和右子树高度的最大值 + 1
    public int getHeight(treeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight,rightHeight) + 1;
    }

    // 检测值为value的元素是否存在
    //思路：通过递归在左右子树分别找
    public treeNode find(treeNode root, int value){
        if(root == null){
            return null;
        }

        if(root.val == value){
            return root;
        }


        treeNode lefttree = find(root.left,value);
        if(lefttree != null){
            return lefttree;
        }


        treeNode  righttree = find(root.right,value);
        if(righttree != null){
            return righttree;
        }

        return null;
    }

    //层序遍历
    public void levelOrder(treeNode root){
        Queue<treeNode> queue = new LinkedList();
        treeNode cur = root;
        queue.offer(root);

        while(!queue.isEmpty()){
            cur = queue.poll();
            System.out.print(cur.val + " ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }


        System.out.println();
    }

    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(treeNode root){
        Queue<treeNode> queue = new LinkedList();
        treeNode cur = root;
        queue.offer(root);

        while(!queue.isEmpty()){
            cur = queue.poll();
            if(cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                break;
            }
        }

        while(!queue.isEmpty()){
            if(queue.peek() != null){
                return false;
            }
            queue.poll();
        }

        return true;
    }

}
